# -*- coding: utf-8 -*-
from queue import Queue

TRADE_MAP = {
    'score': {
        'cd': 5,
        'post': 0,
    },
    'post': {
        'drum': 35,
        'gutar': 30,
    },
    'cd': {
        'drum': 20,
        'gutar': 15
    },
    'drum': {
        'piano': 10
    },
    'gutar': {
        'piano': 20
    },
    'piano': {}
}

# TRADE_MAP = {
#     '0': {
#         '1': 5,
#         '2': 2,
#     },
#     '1': {
#         '3': 4,
#         '4': 2,
#     },
#     '2': {
#         '1': 8,
#         '4': 7
#     },
#     '3': {
#         '5': 3
#     },
#     '4': {
#         '5': 1
#     }
# }

START = 'score'
END = 'piano'


def get_best_road():
    infinity = float('inf')
    length = {START: 0}
    parent = {}
    unhandled_node = set()
    nodes = set(TRADE_MAP.keys())

    def set_smallest(key, value, p_key, length=length, parent=parent):
        if key not in length:
            length[key] = infinity
        if value < length[key]:
            length[key] = value
            parent[key] = p_key

    def get_smallest_node(unhandled_node, length):
        if len(unhandled_node) < 2:
            return list(unhandled_node)[0]
        unhandle_length = {k: length[k] for k in unhandled_node}
        smallest = unhandle_length.keys()[0]
        for i in unhandle_length:
            smallest = i if length[i] < length[smallest] else smallest
        return smallest

    queue = Queue()
    queue.put(START)
    node_count = len(nodes)
    while True:
        # import pdb; pdb.set_trace()
        if queue.empty():
            if len(unhandled_node) == 0:
                break
            else:
                queue.put(unhandled_node.pop())
        key = queue.get()
        for node in TRADE_MAP[key]:
            set_smallest(node, length[key] + TRADE_MAP[key][node], key)
            if node not in unhandled_node:
                unhandled_node.add(node)
        smallest_node = get_smallest_node(unhandled_node, length)
        print '%s\n%s\n' % (smallest_node, unhandled_node)
        unhandled_node.remove(smallest_node)
        if smallest_node != END:
            queue.put(smallest_node)

    key = END
    road = []
    # print parent
    while True:
        road.append(key)
        if key == START:
            break
        key = parent[key]
    road = road[::-1]

    print 'smallest length: %s' % length[END]
    print 'smallest road: %s' % ' -> '.join(road)


def get_best_road1():
    cost = {START: 0}
    parent = {}
    processd = []
    infinity = float('inf')

    def get_low_cost_node(cost, processd):
        low_cost = infinity
        low_cost_node = None
        for node in cost:
            if cost[node] < low_cost and node not in processd:
                low_cost, low_cost_node = cost[node], node
        return low_cost_node

    low_cost_node = 'score'
    while low_cost_node is not None:
        cur_cost = cost[low_cost_node]
        for neighbor in TRADE_MAP[low_cost_node]:
            new_cost = cur_cost + TRADE_MAP[low_cost_node][neighbor]
            if neighbor not in cost:
                cost[neighbor] = infinity
            if cost[neighbor] > new_cost:
                cost[neighbor] = new_cost
                parent[neighbor] = low_cost_node
        processd.append(low_cost_node)
        low_cost_node = get_low_cost_node(cost, processd)

    key = END
    road = []
    # print parent
    while True:
        road.append(key)
        if key == START:
            break
        key = parent[key]
    road = road[::-1]

    print cost['piano']
    print 'lower cost road: %s' % ' -> '.join(road)


if __name__ == '__main__':
    # get_best_road()
    get_best_road1()
